package Lee_code;

import javafx.util.Pair;

import java.util.*;

/**
 * @author blh
 * @date 2024年10月25日 10:05
 * 插入区间
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，
 * 其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，
 * 并且 intervals 按照 starti 升序排列。
 * 同样给定一个区间 newInterval = [start, end]
 * 表示另一个区间的开始和结束。
 */
public class Lee_57_1025 {
    public int[][] insert(int[][] intervals, int[] newInterval) {

        List<Pair<Integer, Integer>> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(new Pair<>(interval[0], interval[1]));
        }
        list.add(new Pair<>(newInterval[0], newInterval[1]));
        // 按照第一个进行排序
        list.sort(Comparator.comparingInt(Pair::getKey));
        // 新建队列
        Deque<Pair<Integer, Integer>> deque = new ArrayDeque<>();

        for (Pair<Integer, Integer> pair : list) {
            if (deque.isEmpty()) {
                deque.offer(pair);
                continue;
            }
            if (deque.peekLast().getValue() >= pair.getKey()) {
                Pair<Integer, Integer> pre = deque.pollLast();
                Pair<Integer, Integer> cur = new Pair<>(pre.getKey(), Math.max(pair.getValue(), pre.getValue()));
                deque.offer(cur);
            } else {
                deque.offer(pair);
            }
        }
        int size = deque.size();
        int[][] res = new int[size][2];
        int index = 0;
        for (Pair<Integer, Integer> pair : deque) {
            res[index][0] = pair.getKey();
            res[index][1] = pair.getValue();
            index++;
        }

        return res;
    }
}
